package com.berchen.算法.排序;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int size = 80000;
        int[] testArr = new int[size];
        for (int i = 0; i < size; i++) {
            testArr[i] = (int) (Math.random() * size);
        }

        Instant start=Instant.now();
        mergeSort(testArr,0, testArr.length-1,new int[testArr.length]);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); // 18
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 分
     */
    public static void mergeSort(int[]arr ,int start ,int end ,int [] temp){
        int mid=(start+end)/2;
        if (start<end){
            mergeSort(arr,start,mid,temp);
            mergeSort(arr,mid+1,end,temp);
            // 合并
            sort(arr,start,mid,end,temp);
        }
    }

    /**
     * 合
     */
    public static void sort(int[] arr,int start,int mid ,int end ,int[] temp){

        int tempIndex=0;
        int left=start;
        int right=mid+1;
        while (left<=mid&&right<=end){
            if(arr[left]<arr[right]){
                temp[tempIndex++]=arr[left++];
            }else {
                temp[tempIndex++]=arr[right++];
            }
        }
        while (left<=mid){
            temp[tempIndex++]=arr[left++];
        }
        while (right<=end){
            temp[tempIndex++]=arr[right++];
        }
        int arrIndex=start;
        tempIndex=0;
        while (arrIndex<=end){
            arr[arrIndex++]=temp[tempIndex++];
        }
    }

}
